#include <set>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

/*
array = {13, 3, 1, 2, -6, 5, -8, 6}
target 0

找到 array 中**所有**三个数字相加等于 target 的组合

{
  {-8, 2, 6},
  {-8, 3, 5},
  {-6, 1, 5}
}
*/
/*
T: O(n^3) n -> array.size()
S: O(n)   n -> array.size()
*/
set<vector<int>> threeNumberSum(const vector<int> &array, int target) {
  set<vector<int>> result{};
	
	for (int i = 0; i < array.size() - 2; ++i) {
		for (int j = i + 1; j < array.size() - 1; ++j) {
			for (int k = j + 1; k < array.size(); ++k) {
				if (array[i] + array[j] + array[k] == target) {
					result.insert({array[i], array[j], array[k]});
				}			
			}
		}
	}
	
  return result;
}

/*
target = 0
array = {13, 3, 1, 2, -6, 5, -8, 6}

             Vcurr
array = {-8, -6, 1, 2, 3, 5, 6, 13}
                 ^l 
                                ^r

sum = array[curr] + array[l] + array[r] = 1
sum > target
*/


int main(int argc, char const *argv[])
{
  /* code */
  
  return 0;
}

